
//922.按奇偶排序数组II
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        //将偶数放在前面，将奇数放在后面
        //使用相向双指针进行实现，从让left向右走找奇数;让right向左走找偶数
        int n=nums.size();
        int left=0,right=n-1;
        while(left<n&&right>0)
        {
            while(left<n&&nums[left]%2==0) left+=2;  //找奇数 
            while(right>0&&nums[right]%2==1) right-=2;  //找偶数

            if(left<n&&right>0)
            swap(nums[left],nums[right]);  //将奇偶进行交换
        }
        return nums;
    }
};